package com.mc.graph;

import java.util.Stack;

/**
 * 检测图是否包含有向环
 * @author MC
 *
 */
public class DirectedCycle {
	private boolean marked[];
	private boolean onStack[];//递归调用的栈上的所有顶点
	private int edgeTo[];//记录路径
	private Stack<Integer> cycle;
	public DirectedCycle(Digraph G){
		marked = new boolean[G.V()];
		onStack = new boolean[G.V()];
		edgeTo = new int[G.V()];
		for(int v=0;v<G.V();v++){
			if(!marked[v])
				dfs(G,v);
		}
	}
	private void dfs(Digraph G, int v){
		marked[v] = true;
		onStack[v] = true;
		for(int w:G.adj(v)){
			if(this.hasCycle())return;
			else if(!marked[w]){
				edgeTo[w]=v;
				dfs(G,w);
			}
			else if(onStack[w]){//该点已经访问过，判断此时是否成环
				cycle = new Stack<Integer>();
				for(int x=v;x!=w;x=edgeTo[x]){
					cycle.push(x);
				}
				cycle.push(w);
				cycle.push(v);
			}
		}
		onStack[v]=false;
	}
	public boolean hasCycle(){
		return cycle!=null;
	}
	public Iterable<Integer> cycle(){
		return cycle;
	}
}
